package Acwing.数学知识;

import java.util.Scanner;

/**
 * @Title: myKsm
 * @Author 贾金博
 * @Package Acwing.数学知识
 * @Date 2025/4/11 下午6:04
 * @description: 快速幂
 */
public class myKsm {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t -- > 0 ) {
            long a = sc.nextInt();
            long b = sc.nextInt();
            long p = sc.nextInt();
            System.out.println(ksm(a, b, p));
        }
    }

    // 自定义快速幂
    private static long ksm(long a, long b, long p) {
        long ret = 1;
        while(b != 0 ) {
            if((b & 1) != 0) {
                ret = ret * a % p;
            }
            a = a * a % p;
            b >>= 1;
        }
        return ret;
    }
}
